'''
https://leetcode.cn/problems/minimum-cost-for-tickets/
'''
from functools import cache
from typing import List

import numpy as np


class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        n = len(days)
        duration = [1, 7, 30]

        @cache  # 暴力尝试+记忆化搜索
        def f(i: int) -> int:
            if i == n: return 0
            ans = float('inf')
            for t in range(3):
                end_up = days[i] + duration[t] - 1  # 1,2,3,4,5,6,7
                j = i
                while j < n and end_up >= days[j]:
                    j += 1
                ans = min(ans, costs[t] + f(j))
            return ans

        return f(0)

    # 还行，时间稍慢一点点，空间省了一点点
    def mincostTickets2(self, days: List[int], costs: List[int]) -> int:
        n = len(days)
        duration = [1, 7, 30]
        dp = [float('inf')] * (n + 1)
        for i in range(n + 1, -1, -1):
            for t in range(3):
                end_up = days[i] + duration[t] - 1  # 1,2,3,4,5,6,7
                j = i
                while j < n and end_up >= days[j]:
                    j += 1
                dp[i] = min(dp[i], costs[t] + dp[j])
        return dp[0]

    # 还行，时间稍快一点点，空间多了一点点
    def mincostTickets3(self, days: List[int], costs: List[int]) -> int:
        MAX = 396
        dayset = set(days)
        dp = np.full(MAX, np.inf)
        dp[days[-1] + 1:] = 0
        for i in range(days[-1], -1, -1):
            if i in dayset:
                dp[i] = min(dp[i], costs[0] + dp[i + 1], costs[1] + dp[i + 7], costs[2] + dp[i + 30])
            else:
                dp[i] = dp[i + 1]
        return int(dp[0])

    # 常数时间慢了
    def mincostTickets4(self, days: List[int], costs: List[int]) -> int:
        MAX = 396
        dayset = set(days)
        dp = np.full((MAX,3), np.inf)
        dp[days[-1] + 1:] = 0
        for i in range(days[-1], -1, -1):
            if i in dayset:
                dp[i][0] = costs[0] + min(dp[i+1])
                dp[i][1] = costs[1] + min(dp[i+7])
                dp[i][2] = costs[2] + min(dp[i+30])
            else:
                dp[i] = dp[i + 1]
        return int(min(dp[0]))


days = [1, 4, 6, 7, 8, 20]
costs = [2, 7, 15]
print(Solution().mincostTickets3(days, costs))
